package com.zyk.leetcode;

import java.util.*;

/**
 * @author zhangsan
 * @date 2021/5/7 11:06
 */
public class M1611 {

    // 暴力解
    public static int[] divingBoard(int shorter, int longer, int k) {
        if (k == 0) return new int[0];
        if (shorter == longer) return new int[]{k};

        Set<Integer> list = new HashSet<>();
        process(shorter, longer, k - 1, list, 0);
        int N = list.size();
        int[] ans = new int[list.size()];
        int index = 0;
        for (Integer i : list) {
            ans[index++] = i;
        }
        Arrays.sort(ans);
        return ans;
    }

    private static void process(int shorter, int longer, int i, Set<Integer> list, int sum) {
        if (i < 0) {
            list.add(sum);
        } else {
            process(shorter, longer, i - 1, list, sum + shorter);
            process(shorter, longer, i - 1, list, sum + longer);
        }
    }

    // 找规律
    public static int[] dp(int shorter, int longer, int k) {
        if (k == 0) return new int[0];
        if (shorter == longer) return new int[]{k};
        // 最小: shorter * k, 最大longer * k.
        // 中间间隔: longer - shorter
        int step = longer - shorter;
        int min = shorter * k, max = longer * k;
        int size = (max - min) / step - 1 + 2;
        int[] res = new int[size];
        res[0] = min;
        for (int i = 1; i < size; i++) {
            res[i] = res[i - 1] + step;
        }
        return res;
    }

    public static void main(String[] args) {
        int shorter = 4;
        int longer = 10;
        for (int i = 1; i <= 10; i++) {
            System.out.println(i + ": " + Arrays.toString(divingBoard(shorter, longer, i)));
            System.out.println(i + ": " + Arrays.toString(dp(shorter, longer, i)));
        }
//        int shorter = 1;
//        int longer = 1;
//        System.out.println(Arrays.toString(divingBoard(shorter, longer, 10/*100000*/)));
    }


}
